package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 螺旋矩阵
 */

public class Code054 {

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(new Code054().spiralOrder(matrix));
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int row = matrix.length, col = matrix[0].length;

        // 可以将visit用四个边界变量代替
        boolean[][] visited = new boolean[row][col];
        int x = 0, y = 0, direction = 0;
        do {
            ans.add(matrix[x][y]);
            visited[x][y] = true; // 标记为访问过
            int[] next = checkNext(visited, x, y, direction); // 获取下一个位置和方向
            x = next[0];
            y = next[1];
            direction = next[2];
        } while (x != -1 && y != -1);

        return ans;
    }

    public int[] checkNext(boolean[][] matrix, int row, int col, int direction) {
        int[] res = {0, 0, 0};
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int maxX = matrix.length, maxY = matrix[0].length;
        boolean flag = true;

        for (int i = 0; i < 4; i++) {
            row += directions[direction][0];
            col += directions[direction][1];
            if (0 <= row && row < maxX && 0 <= col && col < maxY && matrix[row][col] == false) { // 还在范围内
                res[0] = row;
                res[1] = col;
                res[2] = direction;
                return res;
            } else { // 需要调整方向
                row -= directions[direction][0];
                col -= directions[direction][1];
                direction = (direction + 1) % 4;
            }
            if (i == 3) { // 尝试过全部方向，遍历完成
                flag = false;
            }
        }
        if (!flag) {
            res[0] = -1;
            res[1] = -1;
        }
        return res;
    }
}
